\section{Candidate Selection over Multiple Heterogeneous Datasets}
We target the setting of heterogeneous Web data where there might be only little or no overlap between schemas. That is, the attributes captured in different schemas might be so different such that applying schema matching techniques may yield no or only few correspondences (e.g. same-as mappings) between attributes. We tackle the problem of selecting candidate instances over multiple datasets: for instances of one dataset, called the \emph{source}, the goal is to find instances in other datasets, collectively referred to as the \emph{target} dataset, that might refer to the same real-word object. They are then grouped into candidate sets, which can be further refined through an effective matching technique. Such a candidate set can be seen as a block, which is the result of blocking. We do not use the term blocking because typically, it is applied to one single dataset while here, we need to find candidates in the target datasets for instances of a source dataset. 

We focus on Web data including relational data, XML, RDF and other types of data that can be modeled as graphs $\mathbb{G}$ (e.g. RDF graphs),  where every graph G $\in\mathbb{G}$ is a set of triples $(subject, predicate, object)$.  With respect to this model, instances are nodes that appear at the subject position of triples. In particular, an instance is represented by a set of attribute (predicate) and/or values (object), called \emph{keys}. The key of a source instance is used to retrieve matching candidate instances in the target. The goal is to use only a few discriminative attribute and/or values as keys so that matching candidates can be found quickly. 

%Closely resembling this data model we employ a graph-structured data model: 
%\begin{definition}[Data Model] Web data is are modeled as a set of graphs $\mathbb{G}$, where every graph G $\in\mathbb{G}$ is a set of triples, each of the form (s, p, o) where s $\in$U (called subject), p $\in$ U (predicate) and o $\in$ U $\cup$ L (object). Here, U denotes the set of Uniform Resource Identifiers (URIs) and L the set of literals, which together, form the vocabulary V, i.e. V=U $\cup$ L.  
%\end{definition} 

%With respect to this model, instances are resources that appear at the subject position of triples. An instance representation can be obtained from the data graph as follows:


%\begin{definition}[Instance Representation] The instance representation $IR: \mathbb{G} \times U \rightarrow \mathbb{G}$ is a function, which given an instance $s \in U$ and a graph $G \in \mathbb{G}$, maps $s$ to a set of triples in which $s$ appears as the subject, i.e. $IR(s) = \{ (s, p, o) | (s, p, o) \in G, o \in L \}$. 
%\end{definition} 


%We will use the terms instance and instance representation interchangeably from now on. 
%Thus, only outgoing edges $(s, p, o)$ of an instance $s$ are considered. Further, only triples indicating attribute values (triples $o$ as a literal) are typically used for blocking. 

When attribute information is used, the key is determined by the \emph{key schema}. Let $U_A$ be the set of all attributes of a dataset $G$, the key schema is a subset of attributes, i.e. $U^*_A  \subseteq U_A$. Due the heterogeneous data, the source and target key schemas have to be aligned to find comparable attributes so that comparing their values helps to find candidates.
 
Given the schema $U^*_A$, a key 
%of an instances in $G$ are simply 
is formed by an attribute in $U^*_A$ and its value: 
%-value pairs extracted from the instance description, and its value is the set of all values of the attributes in the key schema. 

\begin{definition}[Schema-based Key] Given $p \in U^*_A$, its corresponding schema-based key for an instance $s$ in $G$ is $K(s) =\{  (p,o) | (s, p, o) \in G \}$. 
\end{definition} 

As opposed to that, no attribute information is used in the schema-agnostic approach such that the key is simply a set of value tokens. More precisely, when a literal value $o$ is considered as a bag of tokens, the key here comprises bags of tokens:

\begin{definition}[Schema-agnostic Key] The schema-agnostic key for an instance $s$ in $G$ is $K(s) =\{ o | (s, p, o) \in G \}$. 
\end{definition} 

Given the key representation for a source instance $s$, candidate selection over the target dataset $G_t$ can be accomplished through a query:

\begin{definition} [Candidate Selection Query]  Given $s$ and $G_t$, the candidate selection query for $s$ is $Q(s, \sim) $ = $\{t_i| K(s) \sim K(t_i), t_i \in G_t\}$, where $\sim$ is an equivalence relation over keys.  
\end{definition} 

Intuitively, we obtain candidates by using $K(s)$ as a query to retrieve all instances in $G_t$ that match $K(s)$. The equivalence relation defined above can be implemented as a function that determines whether two given keys are similar (the same) or not. In fact, different similarity functions can be implemented using different queries with different semantics. In this work, we employ EXACT ($K(t)$ exactly matches $K(s)$), LIKE ($K(t)$ is a substring of $K(s)$), AND (all elements in $K(t)$ are also contained in $K(s)$) and OR (at least one element in $K(t)$ is also contained in $K(s)$). The four candidate selection queries Q(s,EXACT), Q(s,LIKE), Q(s,AND) and Q(s,OR) 
for an instance $s$ in $G$, given $K(s) =$ \{``\verb+eosinophilic+  \verb+pneumonia+"\}, can be expressed in SPARQL to retrieve candidates in the target as: 

\begin{footnotesize}%
\begin{verbatim}
SELECT DISTINCT ?s  
WHERE {?s ?p ``eosinophilic pneumonia'' } 

SELECT DISTINCT ?s  
WHERE {?s ?p ?value FILTER regex(?value,``eosinophilic pneumonia'') } 

SELECT DISTINCT ?s  
WHERE {?s ?p ?value FILTER regex(?value,``eosinophilic'') 
                        && regex(?value,``pneumonia'')} 

SELECT DISTINCT ?s  
 WHERE { {?s ?p ?value FILTER regex(?value, ``eosinophilic'' )} UNION 
         {?s ?p ?value FILTER regex(?value, ``pneumonia'' )	   } }
\end{verbatim}
\end{footnotesize}

Evaluating a selection query for every instance $s_i \in G_s$ yields a set of candidate sets, as illustrated in Fig.~\ref{fig:candidates}.

\begin{figure*}[ht]
\vspace{-20pt}
\centering
\includegraphics[scale=0.55 ]{p25.png}
\caption{Candidate sets for tree source instances.} 
\label{fig:candidates}
\vspace{-10pt}
\end{figure*} 

The same four types of queries apply for both type of keys. However, using schema-based keys requires the source and target key schemas to aligned so that the attribute value in the source can be matched against the corresponding attribute value in the target:

\begin{definition}[Comparable Attribute Pairs] The comparable attribute pairs between two key schemas $s$ and $t$ are defined as $U^{*st}_A$ = $\{(p_s,p_t)| p_s \in U^{*s}_A \land  p_t \in U^{*t}_A  \}$. 
%Elements denoted by $p_s$ and $p_t$ are called the \emph{source keys} and \emph{target keys}, respectively.  
\end{definition} 

Given the comparable attribute pair (\verb+rdf:label,sider:sideEffectName+) and $K(s)=$ \{(\verb+rdf:label+,``\verb+eosinophilic+  \verb+pneumonia+")\}, we can use Q(s, EXACT) for instance to retrieve candidates for $s$ from the target as follows:

\begin{small}%
\begin{verbatim}
SELECT DISTINCT ?s  
WHERE {?s sider:sideEffectName ``eosinophilic pneumonia'' } 
\end{verbatim}
\end{small}

In this work, we discuss how comparable attribute pairs can be derived. Then, we can obtain a set of candidate selection queries. Executing all these queries is expensive, hence we propose to reduce the number of queries that has to be executed for retrieving candidates for every instance in the source. 
%
%Candidate selection can be posed as the problem of finding a query that retrieves a subset $A$ of target instances that are possible matches for a source instance \emph{such that $A$ satisfied a optimization function $F(A)$}. $F(A)$ encapsulates a specific measure that attributes quality to the candidate set $A$. For instance, it may be a function that minimizes the size of A. 

%
%\subsection{Searching Instances} 
%The use of an inverted index over the literal values of the learned key pairs may reduce considerably the amount of comparisons necessary to find candidate matches. Nowadays, mostly of the RDF stores provide such an inverted index for quickly look up an instance via a token-based query. Therefore, we do not propose any particular index implementation, but we assume that the literal values of the instances were indexed in an token-based fashion, and can be searched by a token-based query. 

 
%In SPARQL, a candidate selection query for a schema-agnostic key $K(s)$ is simply the triple pattern $\langle ?s, ?p, K(s) \rangle$, where $?s$ and $?p$ denote variables and $K(s)$ is a constant. It simply returns all triples that match $K(s)$ at the object position. The set of candidates for $s$ is captured by the subject (binding to $?s$) of the resulting triples. Instead of exact matching, key overlap has also been used~\cite{papadakis_efficient_2011}. This can be conceived as using a query, where the tokens in $K(s)$ are not interpreted as a conjunction (AND-semantics) but a disjunction (OR-semantics). The query with OR-semantics returns all triples, which match at least one token in $K(s)$ at the object position. For instance, a SPARQL query retrieving all candidates that either match \verb+eosinophilic+ or \verb+pneumonia+  can be specified as follows: 

%\begin{footnotesize}%
%\begin{verbatim}
%SELECT DISTINCT ?s  
% WHERE { {?s ?p ?key FILTER regex(?key, ``eosinophilic'' )} UNION 
  %       {?s ?p ?key FILTER regex(?key, ``pneumonia'' )	   } }
%\end{verbatim}
%\end{footnotesize}

 
%For a schema-based key, which is a set of triples $(s,p,o)$, the query is a set of corresponding triple patterns $\langle ?s, p, o \rangle$ where the attribute and the value in the triple are used as constants at the predicate and object positions of the corresponding triple pattern. The blocking scheme $U^*_A$ uses to construct the keys are learned for one specific dataset, e.g. the source $G_s$. So far, existing works assume that attributes in $G_s$ and $G_t$ are the same (same dataset) or are pre-aligned through upfront schema matching (similar datasets)~\cite{DBLP:conf/semweb/SongH11}. Clearly, when attributes in $G_s$ and $G_t$ are different such that for attributes in $U^*_A$, there are no corresponding attributes in $G_t$, the queries constructed way do not yield any candidates when evaluated against $G_t$ (because there are no triples in $G_t$ that match the constant $p$ in $\langle ?s, p, o \rangle$). In this work, we provide the first solution towards schema-based blocking in scenarios, where the schemas are heterogeneous/different in this sense. 

\textbf{Solutions}. In particular, we consider two recent proposals as baseline. The first one uses schema-agnostic keys as the technique to find candidates (\emph{S-agnostic})~\cite{papadakis_efficient_2011}. The second baseline is schema-based (\emph{S-based}), which relies on precomputed attribute pairs between the source and target key schemas~\cite{DBLP:conf/semweb/SongH11}. 

%Further, it assumes that all keys are covered by these mappings, i.e. for all attributes $U^*_A$ in $G_s$, there is a mapping that specifies the corresponding attribute in $G_t$. This one also uses key overlap. Let 
%\verb+rdf:label+ be the only key attribute in $U^*_A$ and this attribute is mapped to \verb+sider:sideEffectName+, an attribute in $G_t$.  %The following query would be used by S-based to retrieve candidates in $G_t$: 
%\begin{footnotesize}%
%\begin{verbatim}
%SELECT DISTINCT ?s  
% WHERE  { {?s sider:sideEffectName ?key FILTER regex(?key, ``eosinophilic'' } 
%  UNION {?s sider:sideEffectName ?key FILTER regex(?key, ``pneumonia'' } }
%\end{verbatim}
%\end{footnotesize}
%The DezhaoSong also uses a function $is\_sim(t,t')$ to filter the candidates after they are retrieved by the queries. In this evaluation, we fixed for all approaches, the same similarity function as described before in our method.

Because the attribute pairs are however not known for the datasets in our experiment, we propose a technique for finding comparable attributes. In fact, the technique for finding comparable attributes and selecting keys is the same for \emph{S-based} and \emph{Sonda}, the solution proposed in this work. The difference between the two lies in the branch-and-bound optimization we propose to focus on the keys that are time-efficient (targeting efficiency of candidate selection) and yield best results (targeting effectiveness). In particular, Sonda uses an entropy-based approach for selecting key schemas in $G_s$ and $G_t$ (which is the strategy used for S-based~\cite{DBLP:conf/semweb/SongH11} adopted to this scenario).  Then, only pairs of attributes in $G_s$ and $G_t$ that are comparable are considered for constructing candidate selection queries. Different to S-based, Sonda implements a branch-and-bound optimization that searches through the tree-structured space of all queries that have to be considered to obtain the candidate sets for all instances in $G_s$. It aims to find a best path of queries, representing a minimal set of time-efficient queries that produce high quality results. 

 